using System;
using System.Collections.Generic;
using System.Text;

using Microsoft.Xna.Framework;

namespace HadronData
{
    class LayerNode
    {
        private Bounds m_bounds;
        private List<Edge> m_listEdges;
        private LayerNode m_layerNodeLeftChild, m_layerNodeRightChild;

        public static LayerNode PartitionEdges(List<Edge> p_listEdges)
        {
            LayerNode layerNode = new LayerNode();
            if (p_listEdges.Count <= 4)
            {
                layerNode.Edges = p_listEdges;
                layerNode.UpdateBounds();
                return layerNode;
            }

            Bounds bounds = new Bounds();
            bounds.SetEmpty();
            foreach (Edge edge in p_listEdges)
                edge.ExtendBounds(ref bounds);

            bool bHorizontal = bounds.Width > bounds.Height;
            List<Edge> listEdges1 = new List<Edge>();
            List<Edge> listEdges2 = new List<Edge>();

            float fPartitionValue;
            if (bHorizontal)
                fPartitionValue = bounds.Centroid.X;
            else
                fPartitionValue = bounds.Centroid.Y;

            foreach (Edge edge in p_listEdges)
            {
                if (bHorizontal)
                {
                    if (edge.Midpoint.X <= fPartitionValue)
                        listEdges1.Add(edge);
                    else
                        listEdges2.Add(edge);
                }
                else
                {
                    if (edge.Midpoint.Y <= fPartitionValue)
                        listEdges1.Add(edge);
                    else
                        listEdges2.Add(edge);
                }
            }

            if (listEdges1.Count == 0 || listEdges2.Count == 0)
            {
                layerNode.Edges = p_listEdges;
                layerNode.UpdateBounds();
                return layerNode;
            }
            else
            {
                layerNode.LeftChild = PartitionEdges(listEdges1);
                layerNode.RightChild = PartitionEdges(listEdges2);
                layerNode.UpdateBounds();
                return layerNode;
            }
        }

        public LayerNode()
        {
            m_bounds = new Bounds();
            m_listEdges = new List<Edge>();
            m_layerNodeLeftChild = null;
            m_layerNodeRightChild = null;
        }

        public bool Intersects(Edge p_edge)
        {
            if (!m_bounds.Intersects(p_edge))
                return false;

            foreach (Edge edge in m_listEdges)
                if (p_edge.Intersects(edge))
                    return true;

            if (m_layerNodeLeftChild != null && m_layerNodeLeftChild.Intersects(p_edge))
                return true;

            if (m_layerNodeRightChild != null && m_layerNodeRightChild.Intersects(p_edge))
                return true;

            return false;
        }

        public bool Intersects(Ray p_ray)
        {
            if (!m_bounds.Intersects(p_ray))
                return false;

            foreach (Edge edge in m_listEdges)
                if (edge.Intersects(p_ray))
                    return true;

            if (m_layerNodeLeftChild != null && m_layerNodeLeftChild.Intersects(p_ray))
                return true;

            if (m_layerNodeRightChild != null && m_layerNodeRightChild.Intersects(p_ray))
                return true;

            return false;
        }

        public bool Intersects(Ray p_ray, ref Vector2 p_vecIntersectionPoint)
        {
            if (!m_bounds.Intersects(p_ray))
                return false;

            float fShortestDistance = float.MaxValue;
            Vector2 vecIntersectionPoint = Vector2.Zero;

            bool bIntersction = false;
            foreach (Edge edge in m_listEdges)
            {
                if (!edge.Intersects(p_ray, ref vecIntersectionPoint))
                    continue;

                bIntersction = true;

                float fDistance = p_ray.GetSignedTangentDistance(vecIntersectionPoint);
                if (fShortestDistance > fDistance)
                {
                    p_vecIntersectionPoint = vecIntersectionPoint;
                    fShortestDistance = fDistance;
                }
            }

            if (m_layerNodeLeftChild != null && m_layerNodeLeftChild.Intersects(p_ray, ref vecIntersectionPoint))
            {
                bIntersction = true;
                float fDistance = p_ray.GetSignedTangentDistance(vecIntersectionPoint);
                if (fShortestDistance > fDistance)
                {
                    p_vecIntersectionPoint = vecIntersectionPoint;
                    fShortestDistance = fDistance;
                }
            }

            if (m_layerNodeRightChild != null && m_layerNodeRightChild.Intersects(p_ray, ref vecIntersectionPoint))
            {
                bIntersction = true;
                float fDistance = p_ray.GetSignedTangentDistance(vecIntersectionPoint);
                if (fShortestDistance > fDistance)
                {
                    p_vecIntersectionPoint = vecIntersectionPoint;
                    fShortestDistance = fDistance;
                }
            }

            return bIntersction;
        }

        public bool Intersects(Circle p_circle)
        {
            if (!m_bounds.Intersects(p_circle))
                return false;

            foreach (Edge edge in m_listEdges)
                if (edge.Intersects(p_circle))
                    return true;

            if (m_layerNodeLeftChild != null && m_layerNodeLeftChild.Intersects(p_circle))
                return true;

            if (m_layerNodeRightChild != null && m_layerNodeRightChild.Intersects(p_circle))
                return true;

            return false;
        }

        public bool Intersects(Polygon p_polygon)
        {
            if (!m_bounds.Intersects(p_polygon))
                return false;

            foreach (Edge edge in m_listEdges)
                if (p_polygon.Intersects(edge))
                    return true;

            if (m_layerNodeLeftChild != null && m_layerNodeLeftChild.Intersects(p_polygon))
                return true;

            if (m_layerNodeRightChild != null && m_layerNodeRightChild.Intersects(p_polygon))
                return true;

            return false;
        }

        public void ComputeContactPoints(Edge p_edge, List<ContactPoint> p_listContactPoints)
        {
            if (!m_bounds.Intersects(p_edge))
                return;

            foreach (Edge edge in m_listEdges)
                edge.ComputeContactPoints(p_edge, p_listContactPoints);

            if (m_layerNodeLeftChild != null)
                m_layerNodeLeftChild.ComputeContactPoints(p_edge, p_listContactPoints);

            if (m_layerNodeRightChild != null)
                m_layerNodeRightChild.ComputeContactPoints(p_edge, p_listContactPoints);
        }

        public void ComputeContactPoints(Ray p_ray, List<ContactPoint> p_listContactPoints)
        {
            if (!m_bounds.Intersects(p_ray))
                return;

            foreach (Edge edge in m_listEdges)
                edge.ComputeContactPoints(p_ray, p_listContactPoints);

            if (m_layerNodeLeftChild != null)
                m_layerNodeLeftChild.ComputeContactPoints(p_ray, p_listContactPoints);

            if (m_layerNodeRightChild != null)
                m_layerNodeRightChild.ComputeContactPoints(p_ray, p_listContactPoints);
        }

        public void ComputeContactPoints(Circle p_circle, List<ContactPoint> p_listContactPoints)
        {
            if (!m_bounds.Intersects(p_circle))
                return;

            foreach (Edge edge in m_listEdges)
                edge.ComputeContactPoints(p_circle, p_listContactPoints);

            if (m_layerNodeLeftChild != null)
                m_layerNodeLeftChild.ComputeContactPoints(p_circle, p_listContactPoints);

            if (m_layerNodeRightChild != null)
                m_layerNodeRightChild.ComputeContactPoints(p_circle, p_listContactPoints);
        }

        public void ComputeContactPoints(Polygon p_polygon, List<ContactPoint> p_listContactPoints)
        {
            if (!m_bounds.Intersects(p_polygon))
                return;

            foreach (Edge edge in m_listEdges)
                edge.ComputeContactPoints(p_polygon, p_listContactPoints);

            if (m_layerNodeLeftChild != null)
                m_layerNodeLeftChild.ComputeContactPoints(p_polygon, p_listContactPoints);

            if (m_layerNodeRightChild != null)
                m_layerNodeRightChild.ComputeContactPoints(p_polygon, p_listContactPoints);
        }

        public void ComputeContactPoints(Geometry p_geometry, List<ContactPoint> p_listContactPoints)
        {
            if (p_geometry is Edge)
                ComputeContactPoints((Edge)p_geometry, p_listContactPoints);
            else if (p_geometry is Circle)
                ComputeContactPoints((Circle)p_geometry, p_listContactPoints);
            else if (p_geometry is Polygon)
                ComputeContactPoints((Polygon)p_geometry, p_listContactPoints);
        }

        public void UpdateBounds()
        {
            m_bounds.SetEmpty();
            foreach (Edge edge in m_listEdges)
                edge.ExtendBounds(ref m_bounds);

            if (m_layerNodeLeftChild != null)
            {
                m_layerNodeLeftChild.UpdateBounds();
                m_bounds.ExtendTo(m_layerNodeLeftChild.Bounds);
            }

            if (m_layerNodeRightChild != null)
            {
                m_layerNodeRightChild.UpdateBounds();
                m_bounds.ExtendTo(m_layerNodeRightChild.Bounds);
            }
        }

        public Bounds Bounds
        {
            get { return m_bounds; }
        }

        public List<Edge> Edges
        {
            get { return m_listEdges; }
            set { m_listEdges = value; }
        }

        public LayerNode LeftChild
        {
            get { return m_layerNodeLeftChild; }
            set { m_layerNodeLeftChild = value; }
        }

        public LayerNode RightChild
        {
            get { return m_layerNodeRightChild; }
            set { m_layerNodeRightChild = value; }
        }
    }
}
